package LeetCode.binTree_LeetCode;

import bin_tree.MaxHeap.MaxHeap;

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

class Num1046 {
    public int lastStoneWeight(int[] stones) {
        MaxHeap(stones);
        while(data.size() == 1){
            int MaxNum = extractMax();
            int maxNum = extractMax();
            if(MaxNum - maxNum == 0){
                continue;
            }else {
                data.add(MaxNum - maxNum);
            }
        }
        return data.get(0);
    }
    List<Integer> data;
    public void MaxHeap(int size){
        data = new ArrayList<>(size);
    }
    //堆化
    public void MaxHeap(int arr[]){
        data = new ArrayList<>(arr.length);
        for (int i : arr) {
            data.add(i);
        }
        for (int i = pareat(data.size() - 1); i >= 0; i--) {
            siftDowm(i);
        }
    }
    public boolean isEmpty(){
        return data.size() == 0;
    }

    //根据K的索引找到父节点的索引
    private int pareat(int k){
        return (k - 1) >> 1;
    }

    //根据根据K的索引找到左子树节点的索引
    private int leftChild(int k){
        return (k << 1) + 1;
    }

    //根据根据K的索引找到右子树节点的索引
    private int rightChild(int k){
        return (k << 1) + 2;
    }

    //添加
    public void add(int val){
        data.add(val);

        //进行元素的上浮操作
        siftUP(data.size() - 1);
    }
    public int extractMax() {
        if (isEmpty()) {
            throw new NoSuchElementException("Heap is empty!extract false!");
        }
        int maxNum = data.get(0);
        //将数组末尾元素顶到堆顶
        data.set(0,data.get((data.size()) - 1));
        //删除末尾元素
        data.remove(data.size()-1);
        //进行元素的下沉
        siftDowm(0);
        return maxNum;
    }

    //下沉
    private void siftDowm(int k) {
        while(leftChild(k) < data.size()){
            int maxNum = leftChild(k);
            if(maxNum + 1 < data.size() && data.get(maxNum) < data.get(maxNum + 1)){
                maxNum = maxNum + 1;
            }
            if(data.get(k) >= data.get(maxNum)){
                break;
            }else{
                swap(k,maxNum);
                k = maxNum;
            }
        }
    }

    private void siftUP(int k) {
        while(k > 0 && data.get(k) > data.get(pareat(k))){
            //交换当前节点和父节点的值
            swap(k,pareat(k));
            k = pareat(k);
        }
    }

    private void swap(int i, int j) {
        int temp = data.get(i);
        data.set(i,data.get(j));
        data.set(j,temp);
    }
}